# 合并两个有序数组： https://leetcode-cn.com/problems/merge-sorted-array/submissions/

class Solution:
    def merge(self, nums1: list, m: int, nums2: list, n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        如果使用额外的数组，就是归并排序的步骤
        不使用额外数组，那么就是 插入排序的步骤, 但是是逆着推的
        前m个元素是有序的， 后面n个往有序数组里插入， 这就是插入排序的思想，不过是倒着求插入位置。然后移动插入即可~
        """
        
        cur = k = m - 1
        # 从后往前遍历每一个nums2的元素
        for i in range(n-1, -1 , -1):
            # 如果元素大于 nums1的最后一个，一定是最大的，放到最后
            if nums1[m-1] < nums2[i]:
                nums1[m + i] = nums2[i]
            else:
                # 否则移动元素找到合适位置插入，与插入排序思想是一致的
                while cur >= 0 and nums1[cur] > nums2[i]:
                    cur -= 1
                # 找到插入位置后，移出空位
                for j in range(k, cur, -1):
                    nums1[j+1] = nums1[j]
                # 插入
                nums1[cur + 1] = nums2[i]
                # 记录有序的最后一个元素下标，方便后移
                k += 1


# 优化！
class Solution:
    def merge(self, nums1: list, m: int, nums2: list, n: int) -> None:
        """
            利用两个数组是有序的特性。更简单的三指针写法
        """
        i, j, k = m-1, n-1, m+n-1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1

            k -= 1